题解 CF1360C@洛谷 | 1360C@Codeforces 【Similar Pairs】

结论题。

自己列了几次找了一下规律,发现有两个数差为 11 则必定可以,否则看奇偶数的个数。

找规律思考过程:

  1. 如果有两个数差为 11,则必有一奇一偶。
  2. 奇数个数与偶数个数的奇偶性必然相同。(因为总数是偶数个)
  3. 去掉所有差为一的数,剩余的数仍然满足 22
  4. 如果剩余的数中奇数个数和偶数个数均为奇数,则将一对差为一的数拿出用于奇偶数对。(如果没有差为一的数,就不可能完成)
  5. 否则将剩余的数按照奇数、偶数分组即可。

综上,如果有差为一的数,肯定能完成任务;否则如果奇偶数个数为奇数,不能完成,为偶数可以完成。

代码:

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;

int T, n, a[51];

int main() {
	scanf("%d", &T);
	while(T--) {
		scanf("%d", &n);
		int odd = 0, even = 0;
		for(int i=1;i<=n;i++) {
			scanf("%d", &a[i]);
			if(a[i] & 1) {
				++odd;
			}
			else {
				++even;
			}
		}
		sort(a+1, a+1+n);
		bool book = false;
		for(int i=2;i<=n;i++) {
			if(a[i] - a[i-1] == 1) {
				book = true;
				break;
			}
		}
		if(book) {
			puts("YES");
		}
		else if(even % 2 == 0 && odd % 2 == 0) {
			puts("YES");
		}
		else {
			puts("NO");
		}
	}
	return 0;
}